package list;

import java.util.HashMap;

/**
 * 题目：复杂链表的深拷贝
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，
 * 另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，
 * 并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 * <p>
 * 解题思路：
 * 比较简单的方式就是使用一个map先存入所有的节点，先遍历一遍
 * 然后再循环一次，从map里面获取到相应的节点，random节点这些拼装为一个新的list节点
 * @Author Gavin
 * @date 2022.08.06 21:10
 */
public class list_14 {
    public RandomListNode clone(RandomListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new RandomListNode(head.label);
        }

        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        while (head != null) {
            //这一步就是最关键的，把每一个节点存入到map中，注意val里面只设置label值，random和next的值在下面循环中进行设置
            map.put(head, new RandomListNode(head.label));
            head = head.next;
        }

        RandomListNode target = new RandomListNode(head.label);
        RandomListNode p = target;
        RandomListNode curr = head;
        while (curr != null) {
            p.next = map.get(curr.next);
            p.random = map.get(curr.random);

            curr = curr.next;
            p = p.next;
        }
        return target;
    }
}
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}